package com.itdaan.portal.common.util;

import java.text.SimpleDateFormat;
import java.util.BitSet;
import java.util.Date;

/**
 * 布隆过滤器
 * @author www.itdaan.com
 */
public class URLBloomFilter {
	private static final int DEFAULT_SIZE = 2 << 24;
	private static final int[] seeds = new int[] { 5, 7, 11, 13, 31, 37, 61 };
	private static BitSet bits = new BitSet(DEFAULT_SIZE);
	private static SimpleHash[] func = new SimpleHash[seeds.length];

	static{
		for (int i = 0; i < seeds.length; i++) {
			func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
		}
	}
	
	public URLBloomFilter() {

	}

	public static void add(String value) {
		for (SimpleHash f : func) {
			bits.set(f.hash(value), true);
		}
	}

	public static boolean contains(String value) {
		if (value == null) {
			return false;
		}
		boolean ret = true;
		for (SimpleHash f : func) {
			ret = ret && bits.get(f.hash(value));
		}
		return ret;
	}

	// 内部类，simpleHash
	public static class SimpleHash {
		private int cap;
		private int seed;

		public SimpleHash(int cap, int seed) {
			this.cap = cap;
			this.seed = seed;
		}

		public int hash(String value) {
			int result = 0;
			int len = value.length();
			for (int i = 0; i < len; i++) {
				result = seed * result + value.charAt(i);
			}
			return (cap - 1) & result;
		}
	}

	public static void main(String[] args) {
		long size = 1<<24;
		System.out.println("存储"+size+"个邮箱");
		System.out.println("存储1<<30个邮箱前的时间："+new SimpleDateFormat("yyyy-MM-dd HH:mm:ss SSS").format(new Date()));
		StringBuffer value = new StringBuffer("");
		for(long i = 0;i < size;i++){
			value.setLength(0);
			value = new StringBuffer("stone2083@yahoo.cnxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx");
			value.append(i);
			URLBloomFilter.add(value.toString());
		}
		System.out.println("存储1<<30个邮箱后的时间："+new SimpleDateFormat("yyyy-MM-dd HH:mm:ss SSS").format(new Date()));
		boolean isexists = URLBloomFilter.contains("stone2083@yahoo.cnxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"+100);
		System.out.println("是否存在:"+isexists);
		System.out.println("判断完某个邮箱是否存在后的时间："+new SimpleDateFormat("yyyy-MM-dd HH:mm:ss SSS").format(new Date()));
	}

}